#include <bits/stdc++.h>
#pragma	GCC	optimize(3)

using namespace std;

struct qr
{
	int	l,r,Ans,pos;
	bool	operator<(const qr& temp)const
	{ if(l!=temp.l)return l<temp.l; return r<temp.r; }
}c[210000];

int	n,m,a[210000],next[210000],pos[210000];
int	f[530000],val[210000];
bool	visited[210000];

bool	cmp(const qr& temp1,const qr& temp2) { return temp1.pos<temp2.pos; }

void	push_down(const int num,const int l,const int r)
{
	if(f[num]!=0x7f7f7f7f)
	{
		if(l!=r)
		{
			f[num<<1]=min(f[num],f[num<<1]);
			f[num<<1|1]=min(f[num],f[num<<1|1]);
		}
		else val[l]=min(val[l],f[num]);
		f[num]=0x7f7f7f7f;
	} return ;
}

void	Change(const int l,const int r,const int num,
		const int s,const int t,const int d)
{
	if(s<=l && r<=t)
	{
		f[num]=min(f[num],d);
		push_down(num,l,r);
		return ;
	}
	int	mid=l+((r-l)>>1); push_down(num,l,r);
	if(s<=mid)Change(l,mid,num<<1,s,t,d);
	if(t>mid) Change(mid+1,r,num<<1|1,s,t,d); return ;
}

int	Query(int l,int r,int num,const int s)
{
	while(l!=r)
	{
		int	mid=l+((r-l)>>1); push_down(num,l,r);
		if(s<=mid)r=mid,num<<=1;
		else	l=mid+1,num=num<<1|1;
	}
	push_down(num,l,r); return val[l];
}

int main()
{
	int	i;
	scanf("%d%d",&n,&m);

	int	t=0;
	memset(f,0x7f,sizeof(f)); memset(val,0x7f,sizeof(val));
	for(i=1;i<=n;++i)
	{
		scanf("%d",&a[i]);
		next[pos[a[i]]]=i,pos[a[i]]=i;
		visited[a[i]]=true;
		while(visited[t])t++; val[i]=t;
	}

	for(i=1;i<=m;++i)
		scanf("%d%d",&c[i].l,&c[i].r),c[i].pos=i;
	sort(c+1,c+m+1);

	int	cur=1;
	for(i=1;i<=n;++i)
	{
		while(c[cur].l==i)
			c[cur].Ans=Query(1,n,1,c[cur].r),cur++;
		if(next[i])Change(1,n,1,i,next[i]-1,a[i]);
		else	Change(1,n,1,i,n,a[i]);
	}

	sort(c+1,c+m+1,cmp);
	for(i=1;i<=m;++i) printf("%d\n",c[i].Ans);
	return 0;
}
